We consider a path planning problem where a\r\nteam of Unmanned Vehicles (UVs) is required to visit a\r\ngiven set of targets. The UVs are assumed to carry\r\ndifferent sensors, and as a result, there are vehicle-target\r\nconstraints that require each UV to visit a distinct subset\r\nof targets. The objective of the path planning problem is\r\nto find a path for each UV such that each target is visited\r\nat least once by some vehicle, the vehicle-target\r\nconstraints are satisfied and the total distance travelled by\r\nthe vehicles is a minimum. This path planning problem is\r\na generalization of the Hamiltonian path problem and is\r\nNP-Hard. We develop a primal-dual heuristic and\r\nincorporate the heuristic in a Lagrangian relaxation\r\nprocedure to find good, feasible solutions and lower\r\nbounds for the path planning problem. Computational\r\nresults show that solutions whose costs are on an average\r\nwithin 14% of the optimum can be obtained relatively\r\nquickly for the path planning problem involving five UVs\r\nand 40 targets.
Loading....